package 斐波那契数列;

import java.util.Date;
//https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
public class Solution {
    //807526948
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
//        System.out.println(fib(45));
        System.out.println(fib(48));
//        System.out.println(fib(48)%1000000007);
//        System.out.println(fib2(48)%1000000007);

//        System.out.println(System.currentTimeMillis() - start);
    }


    public static int fib(int n) {
        int sum = 0;
        int last = 0;
        for (int i = 1; i <= n; i++) {
            if(i == 1){
                sum+= 1;
                //134903163
            }
            else{
                sum = sum + last;
                last = sum - last;
            }
            sum = sum % 1000000007;
            last = last % 1000000007;
        }
        return sum;
    }

    public static int fib2(int n) {
        if(n == 0){
            return 0;
        }
        else if(n == 1){
            return 1;
        }
        else {
            return fib2(n - 1) + fib2(n - 2);
        }
    }
}
